package com.sicheng.lc.杂题.二叉树;

import leetcode.editor.cn.tree.TreeNode;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/3 15:40
 */
public class 最近公共祖先 {
    //https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        // 刚刚进入时的处理
        // 如果当前节点等于 p||q，那么当前节点就是最近公共祖先
        // 原因：因为是先序遍历刚刚进入，所以一定可以保证当前节点的上方是不存在 p||q 的
        if (root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 说明 p q 在当前节点的左右两边，一边一个，所以最近公共祖先就是 root
        if (left != null && right != null) return root;
        // 说明以当前节点为根的子树中不存在 p q
        if (left == null && right == null) return null;
        // 说明 p q 存在于左孩子或右孩子中
        // 至于为什么可以保证是最近的公共祖先，这就要得益于后序遍历的特点
        // 后序遍历是从下往上开始离开节点，所以可以得到最近的公共祖先
        return left == null ? right : left;
    }
}
